package pro.softzhang.algo.lc400;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.knowledge.KBinarySearchTree;

/**
 *
 */
@KBinarySearchTree
public class LC450_DeleteNodeInABST {
    public static void main(String[] args) {

    }

    /**
     * https://leetcode.cn/problems/delete-node-in-a-bst/solution/miao-dong-jiu-wan-shi-liao-by-terry2020-tc0o/
     */
    static
    class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if(root == null) return null;

            if(key > root.val) {
                root.right = deleteNode(root.right, key);
            } else if (key < root.val) {
                root.left = deleteNode(root.left, key);
            } else {
                if (root.left == null) return root.right;
                if (root.right == null) return root.left;

                TreeNode node = root.right;
                while (node.left != null) node = node.left;
                node.left = root.left;
                root = root.right;
            }

            return root;
        }
    }
}
